SRT (프로세스 스케줄링)

SRT(Shortest Remaining Time, 최단 잔여 시간 우선)는 프로세스 스케줄링에서 가장 남은 실행 시간이 짧은 프로세스에게 CPU를 우선 할당하는 선점형 알고리즘이다. SJF (Shortest Job First)의 선점형 버전이며, 대기 시간을 최소화할 수 있는 이상적인 방식으로 간주된다.

1 개념

• 프로세스가 도착하거나 상태가 변경될 때마다 현재 실행 중인 프로세스와 비교하여, 잔여 실행 시간이 더 짧은 프로세스가 있다면 선점
• 잔여 시간이 짧을수록 우선순위가 높다
• 미래 정보(정확한 실행 시간)를 알고 있다는 전제 하에 성능이 최적화됨

2 동작 방식

1. 프로세스가 새로 도착하면, 현재 실행 중인 프로세스의 잔여 시간과 비교
   • 새 프로세스의 남은 실행 시간이 더 짧으면 선점 발생
   • 그렇지 않으면 현재 실행 중인 프로세스를 유지
2. 모든 프로세스가 종료될 때까지 반복

3 예시

프로세스 정보:

프로세스	도착 시간	실행 시간
P1	0	8
P2	1	4
P3	2	2

스케줄링 결과:

• 0–1: P1 실행
• 1–2: P2 도착 → P2가 P1보다 짧음 → P2로 선점
• 2–4: P3 도착 → P3가 P2보다 짧음 → P3로 선점
• 4–6: P2 재개
• 6–14: P1 재개

4 장점

• 평균 대기 시간과 평균 응답 시간이 짧아짐
• 짧은 작업이 길게 기다리는 일이 없음

5 단점

• 실행 시간을 정확히 예측해야 하며, 이는 현실적으로 어렵다
• 긴 작업은 계속해서 선점당할 수 있어 기아(starvation) 발생 가능
• 프로세스가 자주 선점되면 컨텍스트 스위칭 오버헤드 증가

6 실제 활용

• 실제 운영체제는 실행 시간 예측이 어렵기 때문에, SRT는 MLFQ, 완전공정 스케줄러(CFS) 등의 스케줄러 설계에 참고되는 이론적 모델로 사용됨

7 SRT vs SJF

항목	SJF	SRT
선점 여부	비선점형	선점형
교체 시점	현재 프로세스 종료 시	더 짧은 잔여 시간의 새 프로세스 도착 시
응답 시간	길어질 수 있음	더 짧음

8 같이 보기

• SJF (프로세스 스케줄링)
• FCFS (프로세스 스케줄링)
• 라운드 로빈 (프로세스 스케줄링)
• 프로세스 스케줄링
• 선점형 스케줄링

9 참고 문헌

• Silberschatz, A., Galvin, P. B., & Gagne, G. (2020). Operating System Concepts. Wiley
• Tanenbaum, A. S., & Bos, H. (2014). Modern Operating Systems. Pearson